public class InsertionSort {

    private InsertionSort() {}

    // 正向
    public static <E extends Comparable<E>> void sort(E[] data) {
        if (data == null || data.length <= 1)  return;
        for (int i = 0; i < data.length; i++)
            for (int j = i; j > 0 && data[j].compareTo(data[j - 1]) < 0; j--)
                SortingHelper.swap(data,j, j - 1);
    }

    // 反向
    public static <E extends Comparable<E>> void sortReverse(E[] data) {
        if (data == null || data.length <= 1)  return;
        for (int i = data.length - 1; i >= 0; i--)
            for (int j = i; j < data.length - 1 && data[j].compareTo(data[j + 1]) > 0; j++)
                SortingHelper.swap(data, j, j + 1);
    }

    // 插入排序优化： 减少交换操作次数
    public static <E extends Comparable<E>> void sortV3(E[] data) {
        sortV3(data, 0, data.length);
    }

    public static <E extends Comparable<E>> void sortV3(E[] data, int l, int r) {
        if (data == null || r <= 1)  return;
        for (int i = 0; i < r; i++) {
            E cur = data[i];
            int j = i;
            for (; j > 0 && data[j - 1].compareTo(cur) > 0; j--)
                data[j] = data[j - 1];
            data[j] = cur;
        }
    }

}
